1. Technical Field
The present invention relates to an information security technology, in particular, to a technology for obfuscating computer programs.
2. Background Art
In recent years, with widespread use of information communication technology, importance of information security technology is increasingly acknowledged. As one type of information security technology, encryption technology is realized as encryption software, which is a computer program, and is used for conducting secret communication, protecting privacy, confirming communication partners, and so on.
When encryption software is implemented in a computer system such as an information processing device or a communication device, if its secret key, encryption algorithm, and the like are implemented without any additional processing, the secret key will be easily leaked when malicious users analyze (referred to as “program analysis”) these during program execution. Accordingly, tamper-resistant techniques for improving resistance against program analysis are in demand. As one example of a tamper-resistant technique, Patent Document 1 discloses a method to obfuscate programs by tabulating processes such as encryption and the like, including random conversion operations.
FIG. 39 shows the conventional obfuscation method described in Patent Document 1.
According to this conventional obfuscation method, obfuscation processing (steps S9001 to S9002) is applied to a regular program 9000, which is an encryption program or decryption program of symmetric-key cryptography and has not been obfuscated yet, to generate and output an obfuscated program 9002. Detail of this obfuscation method is given below.
According to the conventional obfuscation method, first, multiple program instructions which compose the regular program 9000 are divided into processing 1 to n (n being a natural number) which use keys key1 to keyn of symmetric-key cryptography, respectively, thereby generating a processing division program 9001 including the processing 1 to n (step S9001).
Next, an output value conversion operation π1 and an output value inverse conversion operation π1−1 are inserted immediately after the processing 1, an output value conversion operation π2−1 and an output value inverse conversion operation π2−1 are inserted immediately after the processing 2, an output value conversion operation π3 and an output value inverse conversion operation π3−1 are inserted immediately after the processing 3, . . . , an output value conversion operation πi and an output value inverse conversion operation πi−1 are inserted immediately after the processing i, . . . , and an output value conversion operation πn−1 and an output value inverse conversion operation πn−1−1 are inserted immediately after the processing n−1. Here, πi−1 represents the inverse conversion of the conversion operation πi−1 (i=1, 2, 3, . . . , n−1).
Next, a table RT1 is generated by tabulating the processing 1 and the output value conversion operation π1, a table RT2 is generated by tabulating the output value inverse conversion operation πi−1, the processing 2, and the output value conversion operation π2, a table RT3 is generated by tabulating the output value inverse conversion operation π2−1, the processing 3, and the output value conversion operation π3, . . . , a table RTi+1 is generated by tabulating the output value inverse conversion operation πi−1, the processing i+1, and the output value conversion operation πi+1, . . . , and lastly, a table RTn is generated by tabulating the output value inverse conversion operation πn−1−1 and the processing n. This is how the obfuscated program 9002 including the tables RT1, RT2, . . . , RTn is generated (step S9002).
Here, if the keys key1 to keyn are predetermined fixed numbers, they can be included in the tables as well.
According to the technique described in Patent Document 1, each table RT1, . . . , RTn−1 converts the output value of each processing 1, . . . , n using the output value conversion operations π1, . . . , πn−1, respectively. Thus, input values and output values to/from each table are converted values. Consequently, even with use of the input values and output values of each table, it is difficult to analyze operations performed in each table, which provides resistance against program analysis. In addition, the output value conversion operation z performed in the table RTi is inversely converted by the output value inverse conversion operation πi−1 performed in the table RTi+1 that immediately follows the table RTi. Accordingly, the execution result of the program is the same as that of the regular program before obfuscation.
FIG. 40 shows an example of a table generated according to the conventional obfuscation method. As shown in this figure, for each input value “in” included in a set 9011, an intermediate value a1 is calculated using the processing 1 (step S9003). Following that, for each intermediate value a1, the output value conversion operation π1 which is a random bijective conversion operation is applied to calculate the post-conversion value π1(a1) converted by the output value conversion operation π1 (step S9004). After that, a table RT1 9014 in which the input value “in” and the post-conversion value π1(a1) are associated with each other is created (step S9005).
Therefore, it can be said that the conventional obfuscation method described in Patent Document 1 serves the purpose of obfuscating programs to a certain extent. However, there are needs for an obfuscating technique able to further enhance resistance to program analysis.    Patent Document 1: International Publication Pamphlet No. WO02/46890    Non-Patent Document 1: Tatsuaki Omamoto & Hiroshi Yamamoto, Gendai Angou (Mondern Cryptography), Sangyo Tosho, 1997.    Non-Patent Document 2: H. Cohen, “A Course in Computational Algebraic Number Theory”, GTM 138, Springer-verlag, 1996, P. 9.